package developer.算法.堆.数据流的中位数;

import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author zhangyongkang
 * @time 2025/4/8 11:55
 * @description 中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
 * <p>
 * 例如 arr = [2,3,4] 的中位数是 3 。
 * 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。
 * 实现 MedianFinder 类:
 * <p>
 * MedianFinder() 初始化 MedianFinder 对象。
 * <p>
 * void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
 * <p>
 * double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。
 * <p>
 * 示例 1：
 * <p>
 * 输入
 * ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
 * [[], [1], [2], [], [3], []]
 * 输出
 * [null, null, null, 1.5, null, 2.0]
 * <p>
 * 解释
 * MedianFinder medianFinder = new MedianFinder();
 * medianFinder.addNum(1);    // arr = [1]
 * medianFinder.addNum(2);    // arr = [1, 2]
 * medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2)
 * medianFinder.addNum(3);    // arr[1, 2, 3]
 * medianFinder.findMedian(); // return 2.0
 * 提示:
 * <p>
 * -105 <= num <= 105
 * 在调用 findMedian 之前，数据结构中至少有一个元素
 * 最多 5 * 104 次调用 addNum 和 findMedian
 */
public class MidNum {
    /**
     * /**
     * * Your MedianFinder object will be instantiated and called as such:
     * * MedianFinder obj = new MedianFinder();
     * * obj.addNum(num);
     * * double param_2 = obj.findMedian();
     */

    public static void main(String[] args) {
        MedianFinder3 medianFinder = new MedianFinder3();
        medianFinder.addNum(1);
        medianFinder.addNum(2);
        System.out.println(medianFinder.findMedian());
        medianFinder.addNum(3);
        medianFinder.addNum(4);
        medianFinder.addNum(4);
        System.out.println(medianFinder.findMedian());
    }

    static class MedianFinder3 {
        private Queue<Integer> minQueue;
        private Queue<Integer> maxQueue;

        public MedianFinder3() {
            minQueue = new PriorityQueue<>((a, b) -> b - a);
            maxQueue = new PriorityQueue<>((a, b) -> a - b);
        }

        /**
         * min: 5 4 3 2
         * max: 6 7 8 9
         *
         * @param num
         */
        public void addNum(int num) {
            if (minQueue.isEmpty() || num <= minQueue.peek()) {//如果小于小队列的最大值，那么就先塞进去
                minQueue.offer(num);
                if (minQueue.size() > maxQueue.size() + 1) {
                    maxQueue.offer(minQueue.poll());
                }
            } else {
                maxQueue.offer(num);
                if (maxQueue.size() > minQueue.size()) {
                    minQueue.offer(maxQueue.poll());
                }
            }
        }


        public double findMedian() {
            if (minQueue.size() == maxQueue.size()) {
                return (minQueue.peek() + maxQueue.peek()) / 2.0;
            } else {
                return minQueue.peek();
            }
        }
    }

    /**
     * min:5 4 3 2
     * max:7 8 9 10
     */
    static class MedianFinder {
        //维护一个小队列以及大队列
        //取小队列和大队列的中间值
        PriorityQueue<Integer> queueMin;
        PriorityQueue<Integer> queueMax;

        public MedianFinder() {
            queueMin = new PriorityQueue<>((a, b) -> a - b);
            queueMax = new PriorityQueue<>((a, b) -> b - a);
        }

        public void addNum(int num) {
            if (queueMax.isEmpty() || queueMax.peek() >= num) {
                queueMax.offer(num);
                if (queueMax.size() > queueMin.size() + 1) {
                    queueMin.offer(queueMax.poll());
                }
            } else {
                queueMin.offer(num);
                if (queueMin.size() > queueMax.size()) {
                    queueMax.offer(queueMin.poll());
                }
            }
        }

        public double findMedian() {
            if (queueMin.size() == queueMax.size()) {
                return (queueMin.peek() + queueMax.peek()) / 2.0;
            }
            return queueMax.peek();
        }
    }


    /**
     * 作者：力扣官方题解
     * 链接：https://leetcode.cn/problems/find-median-from-data-stream/solutions/961062/shu-ju-liu-de-zhong-wei-shu-by-leetcode-ktkst/
     * 来源：力扣（LeetCode）
     * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
     */
    class MedianFinderOfficial {
        PriorityQueue<Integer> queMin;
        PriorityQueue<Integer> queMax;

        public MedianFinderOfficial() {
            queMin = new PriorityQueue<Integer>((a, b) -> (b - a));
            queMax = new PriorityQueue<Integer>((a, b) -> (a - b));
        }

        public void addNum(int num) {
            if (queMin.isEmpty() || num <= queMin.peek()) {
                queMin.offer(num);
                if (queMax.size() + 1 < queMin.size()) {
                    queMax.offer(queMin.poll());
                }
            } else {
                queMax.offer(num);
                if (queMax.size() > queMin.size()) {
                    queMin.offer(queMax.poll());
                }
            }
        }

        public double findMedian() {
            if (queMin.size() > queMax.size()) {
                return queMin.peek();
            }
            return (queMin.peek() + queMax.peek()) / 2.0;
        }
    }


}
